public class test06 {
    class Solution {
        public int longestPalindromeSubseq(String s) {
            char[] ch = s.toCharArray();
            int[][] dp = new int[ch.length][ch.length];

            for(int i = ch.length-1;i>=0;i--){
                dp[i][i] = 1;
                for(int j = i+1;j<ch.length;j++){
                    if(ch[i]==ch[j]){
                        dp[i][j] = dp[i+1][j-1]+2;
                    }else{
                        dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                    }
                }
            }
            return dp[0][ch.length-1];
        }
    }
}
